//
//  200. 岛屿数量.swift
//  Top600
//
//  Created by rjb on 2021/8/9.
//

import Foundation

class Solution200 {
    // 岛屿的数量
    // 采用深度优先遍历 然后还要做标记(或者直接在原有的数组上进行修改)
    // 深度优先遍历经常与做标记想关联起来
    func numIslands(_ grid: [[Character]]) -> Int {
        var used: [[Bool]] = Array(repeating: Array(repeating: false, count: grid[0].count), count: grid.count)
        var count = 0
        // 每一个点都得尝试
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                let isLand = backTrace(grid, &used, row: i, colomn: j)
                if isLand {
                    count += 1
                }
            }
        }
        return count
    }
    @discardableResult
    func backTrace(_ grid: [[Character]], _ used: inout [[Bool]],row: Int, colomn: Int) -> Bool {
        let rowCount = grid.count
        let colomnCount = grid[0].count
        guard row >= 0, colomn >= 0, row < rowCount, colomn < colomnCount else {
            return false
        }
        // 如果已经访问过
        if used[row][colomn] == true {
            return false
        }
       
        // 如果当前节点是岛屿
        if grid[row][colomn] == "0" {
            return false
        }
        
        // 标记本节点访问过
        used[row][colomn] = true
        
        // 向上
        backTrace(grid, &used, row: row - 1, colomn: colomn)
        // 向下
        backTrace(grid, &used, row: row + 1, colomn: colomn)
        // 向左
        backTrace(grid, &used, row: row, colomn: colomn - 1)
        // 向右
        backTrace(grid, &used, row: row, colomn: colomn + 1)
        return true
    }
    
    static func test() {
        let solution = Solution200()
        let grid:[[Character]] = [
            ["1","1","1","1","0"],
            ["1","1","0","1","0"],
            ["1","1","0","0","0"],
            ["0","0","0","0","0"]
        ]
        let result = solution.numIslands(grid)
        print(result)
    }
}
